package com.lans.alg;

/**
 * @author: lans
 * @date: 2025/3/12
 * @name: 刘宇
 */
public class DijstraAlg {

    public static void main(String[] args) {
        //二维数组来描述顶点之间的距离
        int vertex = 7;
        int[][] matrix = new int[vertex][vertex];
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = 10000;//默认10000
            }
        }
        matrix[0][1] = 6;
        matrix[1][2] = 5;
        matrix[0][3] = 2;
        matrix[3][1] = 7;
        matrix[3][4] = 5;
        matrix[1][5] = 3;
        matrix[4][5] = 5;
        matrix[4][6] = 1;
    }

    /**
     *
     * @param matrix 邻接矩阵数组
     * @param source 起始定点
     */
    public static void dijstra(int[][] matrix,int source){
        //最短路径
        int[] shorttest = new int[matrix.length];

        //是否存在最短路径
        int[] visited = new int[matrix.length];

        //用来计算顶点到顶点路径
        String[] path = new String[matrix.length];
        for(int i=0;i<matrix.length;i++){
            path[i] = new String(source+"---->"+i);
        }
        //自身到自身的最短距离为0
        shorttest[source] = 0;
        visited[source] = 1;
        for(int i=1;i<matrix.length;i++){
            int min = Integer.MAX_VALUE;//初始化
            int index=-1;
            for(int j=0;j<matrix.length;j++){
                if(visited[j]==0 && matrix[source][j]<min){//没找过且
                    min = matrix[source][j];
                    index = j;
                }
            }
            shorttest[index]=min;
            visited[index]=1;

            for(int m=0;m<matrix.length;m++){
                if(visited[m]==0 &&matrix[source][index]+matrix[index][m]<matrix[source][m]){
                    matrix[source][m]=matrix[source][index]+matrix[index][m];
                    path[m]=path[index]+"--->"+m;
                }
            }
        }
        for(int i=0;i<matrix.length;i++){
            if(i!=source){
                if(shorttest[i]==10000){
                    System.out.println(source+"  到  "+i+" 不可直达");
                }else{
                    System.out.println(source+" 到 "+i+" 最短路径为: "+path[i]+" 最短距离: "+shorttest[i=]);
                }
            }
        }
    }


}